# 给定一个二叉树的 root ，返回 最长的路径的长度 ，这个路径中的 每个节点具有相同值 。 这条路径可以经过也可以不经过根节点。
#  两个节点之间的路径长度 由它们之间的边数表示。
#
#  示例 1:
# 输入：root = [5,4,5,1,1,5]
# 输出：2
#
#  示例 2:
# 输入：root = [1,4,5,4,4,5]
# 输出：2
from com.example.tree.tree_node import TreeNode


class Solution:
    def longestUnivaluePath(self, root: TreeNode) -> int:
        """
        将任何路径（具有相同值的节点）看作是最多两个从其根延伸出的箭头
        具体地说，路径的根将是唯一节点，因此该节点的父节点不会出现在该路径中，而箭头将是根在该路径中只有一个子节点的路径
        那么该问题实际就是：对每个节点，求向左延伸的最长路径和向右延伸的最长路径之和(后序遍历)
            令 dfs(node) 表示为从节点 node 延伸出的最长箭头的长度。
                如果 node.Left 存在且与节点 node 具有相同的值，则该值就会是 1 + dfs(node.left)。
                在 node.right 存在的情况下也是一样。
            在计算箭头长度时，候选答案将是该节点在两个方向上的箭头之和。将这些候选答案记录下来，并更新最大值。
        :param root:
        :return:
        """
        res = 0

        def dfs(node: TreeNode) -> int:
            nonlocal res
            if not node:
                return 0
            leftRes = dfs(node.left)
            rightRes = dfs(node.right)
            if node.left and node.left.val == node.val:
                leftRes += 1
            else:
                leftRes = 0
            if node.right and node.right.val == node.val:
                rightRes += 1
            else:
                rightRes = 0
            if node.left and node.right and node.left.val == node.left.val == node.val:  # 节点和左右子节点都相同，为左右之和
                res = max(res, leftRes + rightRes)
            else:
                res = max(res, leftRes, rightRes)
            return max(leftRes, rightRes)
        dfs(root)
        return res


if __name__ == "__main__":
    #         5
    #   4            5
    # 1    1     5
    root = TreeNode(5)
    root.left, root.right = TreeNode(4), TreeNode(5)
    root.left.left, root.left.right = TreeNode(1), TreeNode(1)
    root.right.left = TreeNode(5)
    # [1, 4, 5, 4, 4, 5]
    #         1
    #   4            5
    # 4    4     5
    root = TreeNode(1)
    root.left, root.right = TreeNode(4), TreeNode(5)
    root.left.left, root.left.right = TreeNode(4), TreeNode(4)
    root.right.left = TreeNode(5)
    #    1
    #             1
    #       1           1
    #   1       1    1
    root = TreeNode(1)
    root.right = TreeNode(1)
    root.right.left, root.right.right = TreeNode(1), TreeNode(1)
    root.right.left.left, root.right.left.right = TreeNode(1), TreeNode(1)
    root.right.right.left = TreeNode(1)
    print(Solution().longestUnivaluePath(root))
